package 剑指II;

import 链表.ListNode;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-08
 **/

public class Jz024反转链表 {

    /**
     * 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
     * <p>
     * 示例 1：
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     * 示例 2：
     * 输入：head = [1,2]
     * 输出：[2,1]
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     *  
     * 提示：
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     *  
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     */

    public ListNode reverseList(ListNode head) {

        ListNode cur = head;
        ListNode last = null;
        ListNode next;

        while (cur != null) {
            next = cur.next;
            cur.next = last;
            last = cur;
            cur = next;
        }

        return last;
    }

    private ListNode first;

    public ListNode reverseListDg(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode listNode = this.dfs(head);
        listNode.next = null;
        return this.first;
    }

    private ListNode dfs(ListNode node) {
        if (node.next == null) {
            this.first = node;
            return node;
        }
        ListNode cNode = this.dfs(node.next);
        cNode.next = node;
        return node;
    }

    public static void main(String[] args) {
        Jz024反转链表 n = new Jz024反转链表();
        ListNode listNode = ListNode.createListNode(new int[]{1, 2, 3, 4, 5, 6, 7, 8});
        ListNode result = n.reverseListDg(listNode);
        ListNode.printListNode(result);
    }

}
